#include<stdio.h>
#include<stdlib.h>

typedef struct Linked {
	int data;
	int later;
}Link;
Link Link1[100005];
int x1[100000], x2[100005], N;
void CreatLink()
{
	int i, j, z;
	scanf("%d%d", &N, &z);
	for (i = 0; i < z; i++) {
		scanf("%d", &j);
		scanf("%d%d", &Link1[j].data, &Link1[j].later);
	}
}
void Removal()
{
	int i, count = 0, k = 0;
	for (i = N; i != -1; i = Link1[i].later) {
		x1[count++] = i;
	}
	N = count;
	for (i = 0; i < count - i; i++) {
		x2[k++] = x1[count - i - 1];
		x2[k++] = x1[i];
	}
}
void Print() {
	int i;
	for (i = 0; i < N; i++)
		if (i == N - 1)
			printf("%05d %d -1\n", x2[i], Link1[x2[i]].data);
		else
			printf("%05d %d %05d\n", x2[i], Link1[x2[i]].data, x2[i + 1]);
}
int main()
{
	CreatLink();
	Removal();
	Print();
}
